package com.onpositive.units;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedHashSet;

public class Ranker {
	
	public static double[] computeRanks( double[] matrix, int size ){
		
		double[] matrix_canonic = new double[ matrix.length ] ;
		ArrayList<Integer> subspacesIndeces = new ArrayList<Integer>() ;
		int[] inversePermutaion = new int[size] ;
		
		alignInvariantSubspaces( matrix, size, matrix_canonic, subspacesIndeces, inversePermutaion ) ;
	
		matrix_canonic = transpose(matrix_canonic, size) ;
		double[] matrix_t = transpose( matrix_canonic, size ) ;
		
		double[] ranks = computeEigenVector( matrix_canonic, matrix_t, subspacesIndeces, size ) ;
		balanceRanks( ranks, subspacesIndeces ) ;
		double[] result = applyInverseTransform( ranks, inversePermutaion ) ;
		
		return result ;
	}

	private static void balanceRanks(double[] ranks, ArrayList<Integer> subspacesIndeces)
	{
		for( int i = subspacesIndeces.size()-1 ; i >1 ; i-- )
		{
			int llb = subspacesIndeces.get(i-2) ;
			int lb  = subspacesIndeces.get(i-1) ;
			int ub  = subspacesIndeces.get( i ) ;
			
			double maxVal = 0 ;
			for( int j = lb ; j < ub ; j++ )
				maxVal = Math.max(maxVal, ranks[j] ) ;
			
			maxVal += 1.0 ;
			
			for( int j = llb ; j < lb ; j++ )
				ranks[j] += maxVal ;
		}
		
	}

	private static void alignInvariantSubspaces(
			double[] matrix,
			int size,
			double[] matrix_canonic,
			ArrayList<Integer> subspacesBounds,
			int[] permutation)
	{
		ArrayList<Subspace> subspaceMap = new ArrayList<Ranker.Subspace>(size) ;
		  
		for( int i = 0 ; i < size ; i++ )
			subspaceMap.add(null) ;
		
		for( int i = 0 ; i < size ; i++ ){
			Subspace subspace = subspaceMap.get(i) ;
			if( subspace != null )
				continue ;
			
			subspace = computeSubspace(
					i,
					matrix,
					size,
					subspaceMap,
					new ArrayList<Integer>(),
					true ) ;
		}
		
		ArrayList<Integer> indexPerLevel = new ArrayList<Integer>() ;
		ArrayList<Integer> subspacePerLevel = new ArrayList<Integer>() ;
		fillIndexArrays( subspaceMap, indexPerLevel, subspacePerLevel ) ;
		
		int[] ib = new int[ indexPerLevel.size() ] ;
		for( int i = 1 ; i < ib.length ; i++ )
			ib[i] = ib[i-1] + indexPerLevel.get(i-1) ;
		
		int[] sb = new int[ subspacePerLevel.size()+1 ] ;
		sb[0] = 0 ;
		for( int i = 1 ; i < sb.length ; i++ )
			sb[i] = sb[i-1] + subspacePerLevel.get(i-1) ;
		
		subspacesBounds.add(0) ;
		for( int i = 0 ; i < subspacePerLevel.size() ; i++ )
			for( int j = 0 ; j < subspacePerLevel.get(i) ; j++ )
				subspacesBounds.add(0) ;		
		
		for( Subspace s : subspaceMap ){
			if( s.processed )
				continue ;
			
			s.processed = true ;
			
			int height = s.height ;
			
			
				for( Integer a : s.indeces )
					try{
						permutation[ ib[height]++ ] = a ;
					}catch(Exception e){
						e.printStackTrace() ;
					}
			try{
				subspacesBounds.set( ++sb[height], s.indeces.size() ) ;
			}	
			catch(Exception e){
				e.printStackTrace() ;
			}
		}
		
		for( int i = 2 ; i < subspacesBounds.size() ; i++ )
			subspacesBounds.set( i, subspacesBounds.get(i-1) + subspacesBounds.get(i) ) ;
		
//		for( int i = 0 ; i < size ; i++ )
//			for( int j = 0 ; j < size ; j++ )
//				matrix_canonic[size*i+j] = matrix[ size*permutation[i]+permutation[j] ] ;
		
		for( int k = 1 ; k < subspacesBounds.size() ; k++ ){
			int lb = subspacesBounds.get(k-1) ;
			int ub = subspacesBounds.get( k ) ;
			
			for( int i = lb ; i < ub ; i++ )
				for( int j = lb ; j < ub ; j++ )
					matrix_canonic[size*i+j] = matrix[ size*permutation[i]+permutation[j] ] ;
		}
		
		for( int i = 0 ; i < size ; i++ )
			if( matrix_canonic[i*size+i] < epsilon )
				matrix_canonic[i*size+i] = 1.0 ;		
		
//		for( int i = 0 ; i < size ; i++ )
//			for( int j = 0 ; j < size ; j++ ){
//				if( matrix_canonic[i*size+j] > epsilon )
//					matrix_canonic[i*size+j] = 1.0 ;
//				else
//					matrix_canonic[i*size+j] = 0.0 ;
//			}
//		
//		double defVal = 1.0/size ;
//		for( int i = 0 ; i < size ; i++ ){
//			boolean allZero = true ;
//			for( int j = 0 ; j < size ; j++ ){
//				if( matrix_canonic[i*size+j] > 0.0 ){
//					allZero= false ;
//					break ;
//				}			 
//			}
//			if( allZero )
//				for( int j = 0 ; j < size ; j++ )
//					matrix_canonic[i*size+j] = defVal ;
//		}
//		
//		for( int i = 0 ; i < size ; i++ ){
//			double sNorm = 0 ;
//			for( int j = 0 ; j < size ; j++ )
//				sNorm += matrix_canonic[ i*size+j ] ;
//
//			if( sNorm < epsilon )
//				continue ;
//			
//			double mult = 1.0/sNorm ;
//			for( int j = 0 ; j < size ; j++ )
//				matrix_canonic[ i*size+j ] *= mult ;								
//		}
	}

	private static void fillIndexArrays(
			ArrayList<Subspace> subspaceMap,
			ArrayList<Integer> indexPerLevel,
			ArrayList<Integer> subspacePerLevel )
	{
		int maxHeight = 0 ;
		for( Subspace s : subspaceMap )
			maxHeight = s.height > maxHeight ? s.height : maxHeight ;
		
		for( int i = 0 ; i < maxHeight+1 ; i++ ){
			indexPerLevel.add(0) ;
			subspacePerLevel.add(0) ;
		}
		
		//LinkedHashSet<Integer> set = new LinkedHashSet<Integer>() ; 
		
		for( Subspace s : subspaceMap )
			s.processed = false ;
		
		for( Subspace s : subspaceMap ){
			
			if( s.processed == true )
				continue ;
			
			s.processed = true ;
			
			int height = s.height ;			
			
			indexPerLevel.set(height, indexPerLevel.get(height) + s.indeces.size() ) ;
			subspacePerLevel.set(height, subspacePerLevel.get(height)+1) ;
			
//			for( int ind : s.indeces ){
//				
//				boolean alreadyGot = set.contains(ind) ;
//				set.add(ind) ;
//			}
		}		
		
		for( Subspace s : subspaceMap )
			s.processed = false ;
	}

	private static class Subspace{
		
		int height ;
		boolean processed = false ;
		ArrayList<Integer> indeces = new ArrayList<Integer>();
		ArrayList<Subspace> subspaces = new ArrayList<Ranker.Subspace>();
		
		public String toString(){
			return indeces.toString() ;
		}
	}
	
	private static class DummySubspace extends Subspace{		
		int loopIndex ;
	}
	
	private static double epsilon = 1.0/( 1 << 16 ) ; 
	private static Subspace computeSubspace(
			int ind,
			double[] matrix,
			int size,
			ArrayList<Subspace> subspaceMap,
			ArrayList<Integer> history,
			boolean isZeroLevel )
	{
		history.add(ind) ;
		subspaceMap.set( ind, new DummySubspace() ) ;
		
		LinkedHashSet<Subspace> subspaces = new LinkedHashSet<Ranker.Subspace>() ;
		LinkedHashSet<Integer> indeces = new LinkedHashSet<Integer>() ;		
		
		int loopIndex = Integer.MAX_VALUE ;
		
		for( int i = 0 ; i < size ; i++ ){
			
			if( Math.abs( matrix[ ind * size + i ] ) < epsilon )
				continue ;
			
			if( history.contains(i) ){
				int j = history.indexOf(i) ;
				indeces.addAll( history.subList(j, history.size() ) ) ;
				loopIndex = Math.min(loopIndex, j ) ;
				continue ;
			}
			
			Subspace subspace_tmp = subspaceMap.get(i);
			if( subspace_tmp != null )
			{
				if( !(subspace_tmp instanceof DummySubspace) )
					subspaces.add( subspace_tmp ) ;
				
				continue ;
			}		
			
			subspaceMap.set( i, new DummySubspace() ) ;
			
			Subspace newSubspace = computeSubspace(
					i,
					matrix,
					size,
					subspaceMap,
					history ,
					false ) ;
			
			if( newSubspace instanceof DummySubspace ){
				loopIndex = Math.min(loopIndex, ((DummySubspace) newSubspace).loopIndex ) ;
				indeces.addAll( newSubspace.indeces ) ;
				subspaces.addAll( newSubspace.subspaces ) ;
			}
			else
				subspaces.add(newSubspace) ;			
		}
		
		indeces.add(ind) ;
		
		
		Subspace result ;
		if ( loopIndex != history.size() && !isZeroLevel  ){
			result = new DummySubspace() ;
			((DummySubspace)result).loopIndex = loopIndex ;			
		}
		else{
			result = new Subspace() ;
			for( Integer i : indeces )
				subspaceMap.set(i, result ) ;
			
			int height = -1 ;
			for( Subspace s : subspaces )
				height = Math.max(height, s.height ) ;
			
			height++ ;
			result.height = height ;			
		}
		
		result.subspaces = new ArrayList<Subspace>(subspaces) ;
		result.indeces = new ArrayList<Integer>( indeces ) ;
		Collections.sort( result.indeces ) ;
		
		history.remove( history.size()-1 ) ;
		return result ;		
	}

	private static double[] computeEigenVector(
			double[] matrix,
			double[] matrix_t,
			ArrayList<Integer> subspacesIndeces,
			int size )
	{
		
		double[] matrix_ = new double[ matrix.length ] ;
		double[] matrix_t_ = new double[ matrix_t.length ] ;
		
		double[] tmp ;
		for( int i = 0 ; i < 3 ; i++ )
		{
			multiply( matrix, matrix_t, matrix_, matrix_t_ , size ) ;
			tmp = matrix_ ;
			matrix_ = matrix ;
			matrix = tmp ;
			
			tmp = matrix_t_ ;
			matrix_t_ = matrix_t ;
			matrix_t = tmp ;
			
			normalize( matrix, matrix_t, size, subspacesIndeces ) ;
		}
		
		double[] result = new double[size] ;
		for( int i = 0 ; i < size ; i++ )
			result[i] = 0 ;
		
		for( int ind = 1 ; ind < subspacesIndeces.size() ; ind++ )
		{
			int lb = subspacesIndeces.get(ind-1) ;
			int ub = subspacesIndeces.get( ind ) ;
			
			for( int i = lb ; i < ub ; i++ )
				for( int j = lb ; j < ub ; j++ )
					result[i] += matrix[ i*size+j ] ;
		}
		
		return result;
	}

	private static void normalize(double[] matrix, double[] matrix_t, int size,	ArrayList<Integer> subspacesIndeces )
	{
		for( int ind = 1 ; ind < subspacesIndeces.size() ; ind++ )
		{
			int lb = subspacesIndeces.get(ind-1) ;
			int ub = subspacesIndeces.get( ind ) ;
			
			double sNorm = 0 ;
			for( int i = lb ; i < ub ; i++ )
				for( int j = lb ; j < ub ; j++ )
				{
					double var = matrix[ i*size+j ] ;
					sNorm += var*var ;
				}
			
			sNorm = Math.sqrt(sNorm) ;
			if( sNorm < epsilon )
				continue ;
			//sNorm /= ( ub-lb ) ;			
			
			double mult = 1.0 / sNorm ;
			for( int i = lb ; i < ub ; i++ )
				for( int j = lb ; j < ub ; j++ ){
					matrix[ i*size+j ] *= mult ;
					matrix_t[ j*size+i ] = matrix[ i*size+j ] ;
				}
			
			//mult = Math.sqrt(mult) ;
			
			for( int i = ub ; i < size ; i++ )
				for( int j = lb ; j < ub ; j++ ){
					matrix[ i*size+j ] *= mult ;
					matrix_t[ j*size+i ] = matrix[ i*size+j ] ;
				}
			
			for( int i = lb ; i < ub ; i++ )
				for( int j = ub ; j < size ; j++ ){
					matrix[ i*size+j ] *= mult ;
					matrix_t[ j*size+i ] = matrix[ i*size+j ] ;
				}
		}
		
	}

	public final static void multiply(double[] matrix, double[] matrix_t, double[] matrix_, double[] matrix_t_, int s )
	{
		for( int i = 0 ; i < s*s ; i++ ){
			matrix_[i]  = 0;
			matrix_t_[i] = 0 ;
		}
		
		double norm = 0 ;
		for( int i = 0 ; i < s ; i++ ){
			for( int j = 0 ; j < s ; j++ ){
				
				double e = matrix[ i*s + j ];
				norm += Math.abs(e) ; 
				double element = 0 ;
				for( int k = 0 ; k < s ; k++ ){
					element += matrix[ i*s + k ] * matrix_t[ j*s + k ] ;					
				}
				matrix_[ i*s + j ] = element ;
				matrix_t_[ j*s + i ] = element ;				
			}			
		}
		if( norm < 100000 )
			return ;
		
		double divisor = 1.0 / norm ;
		
		
		for( int i = 0 ; i < s*s ; i++ ){
			matrix_[i]   *= divisor ;
			matrix_t_[i] *= divisor ;
		}
	}
	
	private static double[] applyInverseTransform(double[] ranks, int[] permutaion) {
		
		double[] result = new double[ ranks.length ] ;
		
		for( int i = 0 ; i < ranks.length ; i++ )
			result[permutaion[i]] = ranks[ i ] ;
		
		return result;
	}


	public static double[] transpose( double[] matrix, int size )
	{
		double[] matrix_t = new double[ matrix.length ] ;
		for( int i = 0 ; i < size ; i++ )
			for( int j = 0 ; j < size ; j++ )
				matrix_t[ j*size+i ] = matrix[ i*size+j ] ;
				
		return matrix_t ;
	}

}
